package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/8 0:37
 */
public class 恰好移动k步到达某一位置的方法数目 {
    //https://leetcode.cn/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/
    static int mod = (int) 1e9 + 7;

    public int numberOfWays(int x, int y, int k) {
        // dp[i,j] 到达i花费j步
        // dp[i,j] = dp[i - 1,j - 1] + dp[i + 1,j - 1]
        // dp[0,0] = 1 到0花费0就是一种情况，其实理解成初始就在原地不动
        //   -k ... -3 -2 -1 1 2 3 4 ... y - x + 1 这是实际上初始停留在0
        //   0  ....         k k+1     ... y-x+k+1
        //  考虑负数 防止越界 可以从0 跨越 k 步 意味着 需要k步抵达-k
        int n = y - x + k;
        long[][] dp = new long[n + 10][k + 1];
        // dp[-k,k] 抵达-k需要k步 为了防止越界向右挪了k单位
        dp[0][k] = 1;
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i <= n; i++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod;
            }
        }
        return (int) dp[n][k];
    }
}
